#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int n;
int a[N];
__int128 b[N],ans;
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
signed main(){
    freopen("india.in","r",stdin);
    freopen("india.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    if(n==2){printf("%lld\n",abs(a[1]-a[2]));return 0;}
    int o=0;
    for(int i=1;i<n;i++) if(a[i]!=0) o=1;
    if(!o){printf("%lld\n",(n-1)*a[n]);return 0;}
    sort(a+1,a+n+1);
    __int128 sum=0;
    for(int i=1;i<=n;i++) b[i]=(__int128)a[i]*n,sum+=a[i];
    for(int i=n;i>=1;i--){
        if(b[i]>sum){
            __int128 c=b[i]-sum;
            b[i]-=c;
            b[i-1]+=c;
            ans+=c*2;
        }
    }
    write(ans/n);
    return 0;
}